home *** CD-ROM | disk | FTP | other *** search
/ Linux Cubed Series 8: LINUX Games / Linux Cubed Series 8 - LINUX Games.iso / games / muds / lpmud312.tar / lpmud312 / otable.c < prev    next >
C/C++ Source or Header  |  1991-10-31  |  4KB  |  185 lines
  1. #include <stdio.h>
  2. #include <string.h>
  3.  
  4. #include "lint.h"
  5. #include "config.h"
  6. #include "interpret.h"
  7. #include "object.h"
  8.  
  9. /*
  10.  * Object name hash table.  Object names are unique, so no special
  11.  * problems - like stralloc.c.  For non-unique hashed names, we need
  12.  * a better package (if we want to be able to get at them all) - we
  13.  * cant move them to the head of the hash chain, for example.
  14.  *
  15.  * Note: if you change an object name, you must remove it and reenter it.
  16.  */
  17.  
  18. char * xalloc();
  19.  
  20. /*
  21.  * hash table - list of pointers to heads of object chains.
  22.  * Each object in chain has a pointer, next_hash, to the next object.
  23.  * OTABLE_SIZE is in config.h, and should be a prime, probably between
  24.  * 100 and 1000.  You can have a quite small table and still get very good
  25.  * performance!  Our database is 8Meg; we use about 500.
  26.  */
  27.  
  28. static struct object ** obj_table = 0;
  29.  
  30. static void init_otable()
  31. {
  32.     int x;
  33.     obj_table = (struct object **)
  34.             xalloc(sizeof(struct object *) * OTABLE_SIZE);
  35.  
  36.     for (x=0; x<OTABLE_SIZE; x++)
  37.         obj_table[x] = 0;
  38. }
  39.  
  40. /*
  41.  * Object hash function, ripped off from stralloc.c.
  42.  */
  43.  
  44. static int ObjHash(s)
  45. char * s;
  46. {
  47.     if (!obj_table)
  48.         init_otable();
  49.  
  50.     return hashstr(s, 100, OTABLE_SIZE);
  51. }
  52.  
  53. /*
  54.  * Looks for obj in table, moves it to head.
  55.  */
  56.  
  57. static int obj_searches = 0, obj_probes = 0, objs_found = 0;
  58.  
  59. static struct object * find_obj_n(s)
  60. char * s;
  61. {
  62.     struct object * curr, *prev;
  63.  
  64.     int h = ObjHash(s);
  65.  
  66.     curr = obj_table[h];
  67.     prev = 0;
  68.  
  69.     obj_searches++;
  70.  
  71.     while (curr) {
  72.         obj_probes++;
  73.         if (!strcmp(curr->name, s)) { /* found it */
  74.         if (prev) { /* not at head of list */
  75.             prev->next_hash = curr->next_hash;
  76.             curr->next_hash = obj_table[h];
  77.             obj_table[h] = curr;
  78.             }
  79.         objs_found++;
  80.         return(curr);    /* pointer to object */
  81.         }
  82.         prev = curr;
  83.         curr = curr->next_hash;
  84.         }
  85.     
  86.     return(0); /* not found */
  87. }
  88.  
  89. /*
  90.  * Add an object to the table - can't have duplicate names.
  91.  */
  92.  
  93. static int objs_in_table = 0;
  94.  
  95. void enter_object_hash(ob)
  96. struct object * ob;
  97. {
  98.     struct object * s;
  99.     int h = ObjHash(ob->name);
  100.  
  101.     s = find_obj_n(ob->name);
  102.     if (s) {
  103.         if (s != ob)
  104.         fatal("Duplicate object \"%s\" in object hash table",
  105.                 ob->name);
  106.         else
  107.         fatal("Entering object \"%s\" twice in object table",
  108.                 ob->name);
  109.     }
  110.         if (ob->next_hash)
  111.         fatal("Object \"%s\" not found in object table but next link not null",
  112.             ob->name);
  113.     ob->next_hash = obj_table[h];
  114.     obj_table[h] = ob;
  115.     objs_in_table++;
  116.     return;
  117. }
  118.  
  119. /*
  120.  * Remove an object from the table - generally called when it
  121.  * is removed from the next_all list - i.e. in destruct.
  122.  */
  123.  
  124. void remove_object_hash(ob)
  125. struct object *ob;
  126. {
  127.     struct object * s;
  128.     int h = ObjHash(ob->name);
  129.  
  130.     s = find_obj_n(ob->name);
  131.  
  132.     if (s != ob)
  133.         fatal("Remove object \"%s\": found a different object!",
  134.             ob->name);
  135.     
  136.     obj_table[h] = ob->next_hash;
  137.     ob->next_hash = 0;
  138.     objs_in_table--;
  139.     return;
  140. }
  141.  
  142. /*
  143.  * Lookup an object in the hash table; if it isn't there, return null.
  144.  * This is only different to find_object_n in that it collects different
  145.  * stats; more finds are actually done than the user ever asks for.
  146.  */
  147.  
  148. static int user_obj_lookups = 0, user_obj_found = 0;
  149.  
  150. struct object * lookup_object_hash(s)
  151. char * s;
  152. {
  153.     struct object * ob = find_obj_n(s);
  154.     user_obj_lookups++;
  155.     if (ob) user_obj_found++;
  156.     return(ob);
  157. }
  158.  
  159. /*
  160.  * Print stats, returns the total size of the object table.  All objects
  161.  * are in table, so their size is included as well.
  162.  */
  163.  
  164. static char sbuf[100];
  165.  
  166. int show_otable_status(verbose)
  167.     int verbose;
  168. {
  169.     if (verbose) {
  170.     add_message("\nObject name hash table status:\n");
  171.     add_message("------------------------------\n");
  172.     sprintf(sbuf, "%.2f", objs_in_table / (float) OTABLE_SIZE);
  173.     add_message("Average hash chain length               %s\n", sbuf);
  174.     sprintf(sbuf, "%.2f", (float)obj_probes / obj_searches);
  175.     add_message("Searches/average search length       %d (%s)\n",
  176.             obj_searches, sbuf);
  177.     add_message("External lookups succeeded (succeed) %d (%d)\n",
  178.             user_obj_lookups, user_obj_found);
  179.     }
  180.     add_message("hash table overhead\t\t\t %8d\n",
  181.         OTABLE_SIZE * sizeof(struct object *));
  182.     return (OTABLE_SIZE * sizeof(struct object *) +
  183.         objs_in_table * sizeof(struct object));
  184. }
  185.